package com.longge;

import java.util.Arrays;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-05-15 01:08
 */
public class CoinChange {
    int[] memo = null;

    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, amount + 1);
        return dfs(coins, amount);
    }

    private int dfs(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (memo[amount] != memo.length) return memo[amount];
        for (int coin : coins) {
            if (amount - coin<0) continue;
            int sub = dfs(coins, amount - coin);
            if (sub == -1) continue;
            memo[amount] = Math.min(sub + 1, memo[amount]);
        }
        memo[amount] = memo[amount] == memo.length ? -1 : memo[amount];
        return memo[amount];
    }

    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        new CoinChange().coinChange(new int[]{186,419,83,408},6249);
        long r = System.currentTimeMillis();
        System.out.println(l-r);
    }
}
